1. Field of the Invention
The present invention relates to an authentication technique for authenticating user""s access rights to resources.
2. Description of the Prior Art
As the prior art belonging to the same field as the present invention there is known a program execution control technique, which comprises:
(1) embedding a user authentication routine in an application program;
(2) the routine checking whether the user who is trying to execute the application possesses a regular key for authentication; and
(3) continuing the execution of the program only when the presence of the key for authentication has been confirmed, or stopping the execution of the program if the answer is negative.
By utilizing this control technique, only a regular user possessing an authentication key is allowed to execute the application program. This technique is in practical use in the software distribution business. As examples of products produced according to this technique are mentioned Sentinel Super Pro (trademark) of Rainbow Technologies, Inc. and HASP (trademark) of Aladdin Knowledge Systems Ltd.
The following is a more detailed explanation of the program execution control technique.
(1) The user who executes a software program possesses an authentication key as a user identifying information. The authentication key is a key for encryption, which is distributed to users by a person who permits the utilization of software, for example a software vender. The authentication key, for the prevention of duplication, is sealed firmly into memory or the like in hardware and is delivered to the associated user by physical means such as mail or the like.
(2) The user loads the hardware with the authentication key incorporated therein into a his or her work station/personal computer by a specified method. For example, the hardware is loaded into a printer port.
(3) When the user starts the application program and the execution of the program reaches the user authentication routine, the program communicates with the hardware which incorporates the user authentication key therein. On the basis of the communication the program checks whether the authentication key is correct or not, and if the key is correct, execution shifts to the next step. On the other hand, if the communication fails and the presence of the authentication key cannot be confirmed, the program itself stops to inhibit subsequent execution.
Identification of the authentication key in the authentication routine is performed in accordance with the following protocol.
(1) The authentication routine generates an appropriate number and transmits it to the key-containing hardware.
(2) The key-containing hardware, using the authentication key contained therein, encrypts the transmitted number and sends it back to the authentication routine.
(3) The authentication routine judges whether the replied number is an anticipated number or not, that is, whether it is a number obtained by encrypting the transmitted number to the hardware with the correct authentication key.
(4) In the case where the replied number coincides with the anticipated number, the execution of the program is continued, while otherwise, the execution of the program is stopped.
In this case, the communication between the application program and the authentication key-containing hardware must differ at every execution even if exchange is made with the same hardware at the same location in the same application. Otherwise, if the contents of communication in a normal execution process are once recorded and if subsequently a reply is made to the application program in accordance with the recorded contents at every execution of program, it becomes possible for even a user not possessing a correct authentication key to execute the program. Such an improper execution of the application program by the reproduction of communication contents is called a replay attack.
To prevent such a replay attack, a random number which is newly generated at every communication is used as the number sent to the key-containing hardware.
The prior art described above involves the problem that at the time of making an application program it is required for the programmer to assume an authentication key of a user in advance and then perform a program protection processing on the basis of the authentication key.
That is, the programmer is required to anticipate a correct reply from the key-containing hardware at the time of programming and then create a program so that the program is executed correctly only upon receipt of a correct reply.
The prior art described above is utilized basically in two ways, both of which, however, involves the following problems.
(1) According to the first method, different authentication keys are provided for different users. More particularly, a different authentication key is provided for each user such as authentication key A for user A and authentication key B for user B.
In this case, it is necessary for the programmer to make a program while changing the authentication routine in the program appropriately for each user. In more particular terms, since the authentication key differs for each user, it is required that the authentication routine in the program be prepared so as to identify the authentication key peculiar to the each user who utilizes the program. In other words, the programmer is required to make as many different programs as the number of users who utilize the program.
In the case where a large number of users are involved, the work for individualizing programs for each user requires intolerable labor for the programmer, and the list of user authentication keys to be managed becomes vast.
(2) According to the second method, the programmer prepares a different authentication key for each application, for example, like authentication key A for application A and authentication key B for application B. And each application program is prepared so as to identify a unique authentication key.
According to this second method, unlike the first method, it is no longer necessary to make a program individually for each user, but the user is required to possess authentication keys by the number of applications to be utilized.
Such a limitation gives rise to the following problems for both programmer and users.
As noted previously, it is necessary that authentication keys be delivered in a firmly sealed state to users. Thus, in contrast with the program itself which can be distributed easily through a network, the distribution of hardware which contains an authentication key must rely on physical means such as mail or the like. This limitation is a heavy burden on the programmer in all of cost, time and packing work.
There arises the inconvenience that even if a user wants to use a certain application, the user must wait for the arrival of hardware with an authentication key sealed therein and cannot use it at once.
To lighten this burden there is adopted a method wherein a plurality of authentication keys are sealed beforehand in hardware, and each time the user is permitted to use a new application, a password for making an unused authentication key in hardware utilizable is given to the user. However, it is apparent that the foregoing problems are basically not solved even by this method. Actually, in commercialization, a design is made so as to permit adjacent connection of plural hardware units.
Thus, even if either of the above two methods is adopted, there still remain problems in point of convenience on both programmer and user sides.
Considering external characteristics of the execution control, the prior art may also be applicable to the protection of mail privacy, access control for file and computer resources, and other ordinary access control for digital contents. However, due to the foregoing problems, it is impossible to apply the prior art to those fields.
The present invention has been accomplished in view of the above-mentioned circumstances and it is an object of the invention to provide a user""s access rights authentication technique capable of solving inconveniences derived from handling of many unique identifying information pieces such as authentication keys which occur on both the user side and the protector side such as an application creator and further capable of easily authenticating a user""s access rights in performing program execution control, the protection of access qualification of digital contents (e.g. static and dynamic images and voice), mail privacy protection, and access control for file and computer resources.
According to the present invention, in order to achieve the above-mentioned object, there is provided a user""s access rights authentication device for authenticating a user""s access rights by verifying the legitimacy of proof data generated for proving the right of the user, the user""s access rights authentication device comprising a first memory means for storing authentication data, a second memory means for storing user unique identifying information, a third memory means for storing a proof support information which is the result of having executed a predetermined calculation, authentication data stored in the first memory means, a proof data generation means which performs a predetermined calculation for both the authentication data held in the first memory means and the user unique identifying information held in the second memory means, to generate proof data, and a proof data verification means which performs a predetermined calculation for both the proof data generated by the proof data generation means and the proof support information held in the third memory means, to verify that the proof data has been generated on the basis of the user unique identifying information. The unique security characteristic information is used as a digital signature key based on a discrete logarithm problem of a linear algebraic group on a finite field (a group constituted by an invertible matrix of a finite field coefficient; hereinafter referred to simply as xe2x80x9calgebraic groupxe2x80x9d).
In the above construction, by introducing the proof support information (access ticket) it is possible to make unique security characteristic information and user unique identifying information independent of each other, so that it suffices for each of the protector side and the user side to prepare only one piece of unique identifying information.
The access ticket is data calculated on the basis of both specific user unique identifying information and unique security characteristic information. Without the knowledge of user unique identifying information, it is difficult to calculate a unique security characteristic information from the access ticket. Only when a correct combination of user unique identifying information and access ticket, namely a combination of user unique identifying information and access ticket calculated on the basis of the user unique identifying information, is inputted, correct proof data is calculated. Therefore, the user holds unique identifying information in advance and the protector side such as a programmer provides unique security characteristic information independently of the unique identifying information which the user possesses, then access ticket is prepared and distributed in accordance with the user unique identifying information and the unique security characteristic information which has been used, for example, in the creation of an application program. By so doing, it is possible to authenticate the user""s access rights to resources such as execution control.
The present invention can be realized also as a method. Further, at least part of the present invention can be realized as a program product.
In connection with the above configuration, the proof data verification means may be provided with a random number generation means so that a random number generated by the random number generation means is stored as authentication data in the first memory means.
The proof data verification means may be configured so as to verify that the proof data generated by the proof data generation means results from performing a predetermined calculation for both authentication data as the above random number and user unique identifying information.
For the above calculation there may be adopted the following method.
First, ElGamal signature is employable. Algebraic group is generally non-commutative, but there will appear only a cyclic subgroup in the following description, so for convenience in notation the group calculation will be described in an additive manner.
To be more specific, in an algebraic group Rover a finite field, if the point with an order of n is assumed to be P, a unique security characteristic information is assumed to be x, and verification information Y corresponding to x is assumed to be a point (Y=xP) on G obtained by multiplying the P by x, then the foregoing proof data generation means generates as proof data both point R on G and a positive integer s, while the foregoing proof data verification means generates a value rt by multiplying the proof support information t stored in the third memory means by a positive integer r determined from R and verifies that the sum of the value obtained by multiplying the Y by the positive integer r determined from R, the value obtained by multiplying R by s and the value obtained by multiplying the P by [(xe2x88x92rt) mod n], on G, is equal to the value obtained by multiplying the point P by m using the authentication data stored in the first memory means (mP=rY+sRxe2x88x92rtP).
Or, in an algebraic group G on a finite field, if the point with an order of n is P, unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof data generation means generates as proof data both point R on G and a positive integer s, while the proof data verification means generates a value rt by multiplying the proof support information t stored in the third memory means by a positive integer r determined from R and verifies that the sum of the value obtained by multiplying the Y by rt and the value obtained by multiplying R by s, on G, is equal to the value obtained by multiplying the point P by m using the authentication data stored in the first memory means (mP=rtY+sR).
Or, in an algebraic group G on a finite field, when the point with an order of n is assumed to be P and for generating, as proof data, both point R on G and a positive integer s, the proof data generation means generates an appropriate random number k, then multiplies the P by k on G, assumes the resulting point to be R (=kP), then uses at least a positive integer f which is determined from the user unique identifying information e stored in the second memory means, a positive integer r determined from point R, and the authentication data m stored in the first memory means, then, under the modulus n, subtracts the product of f and r from m, and multiplies the resulting difference by the inverse of k to calculate s [=(mxe2x88x92rf)kxe2x88x921 mod n], thereby generating proof data R and s.
Or, in an algebraic group G on a finite field, when the point with an order of n is assumed to be P and for generating as proof data both point R on G and a positive integer s, the proof data generating means generates an appropriate random number k, multiplies the P by k on G, assumes the resulting point to be R (=kP), then uses at least a positive integer f generated by performing a predetermined calculation for both the user unique identifying information e stored in the second memory means and information which defines the above algebraic group, a positive integer r determined from point R, the above k, and the authentication data m stored in the first memory means, then, under the modulus n, subtracts the product of f and r from m, and multiplying the resulting difference by the inverse of k to calculate s [=(mxe2x88x92rf)kxe2x88x921 mod n], thereby generating both proof data R and s.
In an algebraic group G on a finite field Fq with q elements, if the point with an order of n on G is assumed to be P, a unique security characteristic information is assumed to be a positive integer x, verification information Y corresponding to the x is assumed to be a point (Y=xP) on G obtained by multiplying the P by x, then the proof support information t stored in the third memory is the data obtained by subtracting a positive integer f from the above x which positive integer f is generated by performing a predetermined calculation for the user unique identifying information e stored in the second memory means, and in generating point R on G and a positive integer s, the proof data generation means may generate an appropriate random number k, multiplies the P by k on G, assume the resulting point to be R (=kP), use the positive integer f, the random number k and the authentication data m stored in the first memory means, then under the modulus n, subtract the product of f and r from m and multiply the resulting difference by the inverse of k to generate s [=(mxe2x88x92rf)kxe2x88x921 mon n], while the proof data verification means may verify that, on G, the sum of the value obtained by multiplying the Y by r, the value obtained by multiplying R by s and the value obtained by multiplying P by [(xe2x88x92rt) mod n] is equal to the value obtained by multiplying P by m using the authentication data (mP=rY+sRxe2x88x92rtP).
In an algebraic group G on a finite field Fq with q elements, if the point with an order of n on G is assumed to be P, unique security characteristic information is assumed to be a positive integer x, and verification information Y corresponding to the x is assumed to be a point (Y=xP) on G obtained by multiplying the P by x, then the proof support information t stored in the third memory means is the data obtained by subtracting a positive integer f from the x which positive integer f is generated by performing a predetermined calculation for both user unique identifying information e stored in the second memory means and the above q and G, and in generating as proof data both point R on G and a positive integer s, the proof data generation means may generate an appropriate random number k, assume the point obtained by multiplying the P by k on G to be R (=kP), use the above positive integer f, the random number k and the authentication data m stored in the first memory means, then, under the modulus n, subtract the product of f and r from m, and multiply the resulting difference by the inverse of k to generate s [=(mxe2x88x92rf)kxe2x88x921 mod n], while the proof data verification means may verify that the sum of the value obtained by multiplying the Y by r, the value obtained by multiplying R by s and the value obtained by multiplying P by [(xe2x88x92rt)mod n], on G, is equal to the value obtained by multiplying P by m using the authentication data (mP=rY+sRxe2x88x92rtP).
In an algebraic group G on a finite field Fq with q elements, if the point with an order of n on G is assumed to be P, a unique security characteristic information is assumed to be a positive integer x, and verification information Y corresponding to the x is assumed to be a point (Y=xP) on G obtained by multiplying the P by x, then the proof support information t stored in the third memory means is the data [t=xxe2x88x921 f (e, n, q, P, G) mod n] obtained by multiplying, under the modulus n, an inverse element xxe2x88x921 of the above x by a non-conflictive function value f (e, n, q, P, G) which depends on the user unique identifying information e stored in the second memory means and also on the above n, q, P and G, and in generating, as proof data, a point R corresponding to the value of r determined from point as well as a positive integer s, the proof data generation means may generate an appropriate random number k, assume the point obtained by multiplying the P by k on G to be R (=kP), use the above e, n, q, P, G, f (e, n, q, P, G) and authentication data m stored in the first memory means, then, under the modulus n, subtract the product of f (e, n, q, P, G) and r from m, and multiply the resulting difference by the inverse of k to generate s {=[mxe2x88x92rf (e, n, q, P, G)] kxe2x88x921 mod n}, while the proof data verification means may verify that, on G, the sum of the value obtained by multiplying the Y by rt and value obtained by multiplying R by s is equal to the value obtained by multiplying P by m using the authentication data (mP=rtY+sR).
There also may be used Nyberg-Rueppel signature.
More specifically, in an algebraic group G on a finite field, given that the point with an order of n is P, a unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof data generation means may generate positive integers r and s as proof data, while the proof data verification means may generate the value rt by multiplying the proof support information t stored in the third memory means by the r, then, on G, calculate the sum K of the value obtained by multiplying the Y by r, the value obtained by multiplying the P by s and the value obtained by multiplying the P by xe2x88x92rt, (K=rY+sPxe2x88x92rtP), and then verify that the difference between the r and the value k determined from point K is congruent with the authentication data m stored in the first memory means, under the modulus n, (mxe2x89xa1rxe2x88x92k mod n).
In an algebraic group G on a finite field, given that the point with an order of n is P, unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, and for generating positive integers r and s as proof data, then the proof data generation means may generate an appropriate random number u, assume the point obtained by multiplying the P by u on G to be V (=uP), then under the modulus n add the value v determined from V and the authentication data m to obtain the value r as the sum (r=m+v mod n), then use a non-conflictive function value f which depends on both user unique identifying information e stored in the second memory means and information which defines the above algebraic group, as well as the above u and r, and subtract the product of f and r from u under the modulus n to obtain the value s as the difference (s=uxe2x88x92rf mod n).
In an algebraic group G on a finite field with q elements, given that the point with an order of n on G is P, a unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof support information t stored in the third memory means is the data [t=xxe2x88x92f (e, n, q, P, G)] obtained by subtracting a non-conflictive function value f (e, n, q, P, G) from the x which value f is dependent on the user unique identifying information e stored in the second memory means and the above n, q, P, G, and for generating positive integers r and s as proof data, the proof data generation means may generate an appropriate random number u, assume the point obtained by multiplying the P by u on G to be V (=uP), then under the modulus n add the value v determined from V and the authentication data m stored in the first memory means to obtain the value r as the sum (r=m+v mod n), use the above e, n, q, P, G and f (e, n, q, P, G), and subtract the product of f (e, n, q, P, G) and r from u under the modulus n to obtain the value s as the difference [s=uxe2x88x92rf (e, n, q, P, G) mod n], while the proof data verification means may calculate on G the sum K of the value obtained by multiplying the Y by r, the value obtained by multiplying P by s and the value obtained by multiplying P by xe2x88x92rt, (K=rY+sPxe2x88x92rtP), and verify that the difference between the r and the value k determined from point K is congruent with the authentication data m under the modulus n (mxe2x89xa1rxe2x88x92k mod n).
Further, there may be used Schnorr signature.
More specifically, in an algebraic group G on a finite field, given that the point with an order of n is P, unique security characteristic information is a positive integer x, and verification information Y corresponding to x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof data generation means may generate positive integers h and s as proof data, while the proof data verification means may generate the value ht by multiplying the proof support information t stored in the third memory means by the positive integer h, then subtract the value obtained by multiplying the P by ht from the sum of the value obtained by multiplying the Y by h and the value obtained by multiplying the P by s to afford the value V as the difference, (V=hY+sPxe2x88x92htP), and verify that a collision-free function value H (v|m), which depends on a combined value of both value v determined from V with the authentication data m stored in the first memory means, is equal to the positive integer h, [hxe2x89xa1H (v|m)].
In an algebraic group G on a finite field, given that the point with an order of n is P, a unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, and for generating positive integers h and s as proof data, then the proof data generation means may generate an appropriate random number k, assume the point obtained by multiplying the P by k on G to be R (=kP), use a collision-free function value H (r|m), which depends on a combined value of both value r determined from R and authentication data m stored in the first memory means, a non-conflictive function value f which depends on both user unique identifying information e stored in the second memory means and information which defines the above algebraic group, the random number k and the positive integer h, and subtract the product of f and h from k under the modulus n to afford the difference s (=kxe2x88x92hf mod n).
In an algebraic group G on a finite field Fq with q elements, given that the point with an order of n on G is P, unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP on G obtained by multiplying the P by x, then the proof support information t stored in the third memory means is the data [t=xxe2x88x92f (e, n, q, P, G)] obtained by subtracting a collision-free function value f (e, n, q, P, G) from the x which value f depends on the user unique identifying information e stored in the second memory and also on the above n, q, P and G, and for generating positive integers h and s as proof data, the proof data generation means may generate an appropriate random number k, assume the point obtained by multiplying the P by k on G to be R (=kP), then use a collision-free function value H (r|m) which depends on a combined value of both value r determined from R with authentication data m stored in the first memory means, as well as the above k, h, e, n, q, P, G and f (e, n, q, P, G), and subtract the product of f (e, n, q, P, G) and h from k under the modulus n to generate the difference s [=kxe2x88x92hf (e, n, q, P, G) mod n], while the proof data verification means may generate the value ht by multiplying the proof support information t by the positive integer h, then subtract the value obtained by multiplying the P by ht from the sum of the value obtained by multiplying the P by s and the value obtained by multiplying the Y by h, on G, to afford the value Rxe2x80x2 (=sP+hYxe2x88x92htP), and verify that the output of a collision-free function H, which receives a combined value of both value rxe2x80x2 determined from Rxe2x80x2 and authentication data m, is equal to h, [h=H(rxe2x80x2|m)].
Further, there may be used DSA signature.
More specifically, in an algebraic group G on a finite field, given that the point with an order of n is P, unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof data generation means may generate positive integers r and s as proof data, while the proof data verification means may generate an inverse element w (=sxe2x88x921 mod n) of s under the modulus n, then generate the value wr by multiplying the r by the w, the value wrt by multiplying the proof support information t stored in the third memory means by the r, and the value wm by multiplying the authentication data m stored in the first memory means by the w, and verify that, on G, the value v determined from the value V (=wrY+wmPxe2x88x92wrtP) is equal to the r under the modulus n (vxe2x89xa1r mod n) which value V results from subtracting the value obtained by multiplying P by wrt from the sum of the value obtained by multiplying Y by wr and the value obtained by multiplying P by wm.
In an algebraic group G on a finite field, given that the point with an order of n is P, unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof data generation means may generate positive integers r and s as proof data, while the proof data verification means may generate an inverse element w (=sxe2x88x921 mod n) of s under the modulus n, further generate the value wrt by multiplying the proof support information t stored in the third memory by the above r and w, and the value wm by multiplying the authentication data m stored in the first memory means by the above w, and verify that, on G, the value v determined from the value V (=wrtY+wmP) is equal to the r under the modulus n (v=r mod n) which value V is the sum of the value obtained by multiplying the Y by wrt and the value obtained by multiplying the P by wm.
In an algebraic group G on a finite field, given that the point with an order of n is P, a unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, and for generating, as proof data, a point R which takes the value r determined from point, as well as a positive integer s, then the proof data generation means may generate an appropriate random number k, assume that the value determined from point R (=kP) obtained by multiplying the P by k on G is r, then use a non-conflictive function value H(m) which depends on the authentication data m stored in the first memory means, a collision-free function value f dependent on both user unique identifying information e and information which defines the above algebraic group, and the above r, and then multiply the reciprocal of k by the difference obtained by subtracting the product of f and r from H(m) under the modulus n to thereby calculate s [=(H(m)xe2x88x92rf)kxe2x88x921 mod n].
In an algebraic group G on a finite field Fq having q number of elements, given that the point with an order of n on G is P, a unique security characteristic information is a positive integer x, and verification information corresponding to x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof support information t stored in the third memory means is the data [t=x+f (e, n, q, P, G)] obtained by adding a collision-free function value f (e, n, q, P, G) to the x which value f depends on the user unique identifying information e stored in the second memory means and also on the above n, q, P and G, and for generating as proof data a point R which takes the value r determined from point, as well as a positive integer s, the proof data generation means may generate an appropriate random number k, assume that the value determined from point R (=kP) obtained by multiplying the P by k on G is r, then use the authentication data m stored in the first memory means, as well as the above e, n, q, P, G and f (e, n, q, P, G), subtract the product of f (e, n, q, P, G) and r from m and multiply the resulting difference by the reciprocal of k, under the modulus n, to generate s {=[mxe2x88x92rf (e, n, q, P, G)] kxe2x88x921 mod n}, while the proof data verification means may generate an inverse element w (=sxe2x88x921 mod n) of s under the modulus n, further generate the value wr by multiplying the r by the w, the value wrt by multiplying the proof support information t stored in the third memory by the r and w, and the value wm by multiplying the m by the w, and verify that, on G, the value v determined from the value V (=wrY+wmPxe2x88x92wrtP) is equal to the r under the modulus n (vxe2x89xa1r mod n) which value V results from subtracting the value obtained by multiplying the P by wrt from the sum of the value obtained by multiplying the Y by wr and the value obtained by multiplying the P by wm.
In an algebraic group G on a finite field Fq with q elements, given that the point with an order of n is P, a unique security characteristic information is a positive integer x, and verification information Y corresponding to the x is a point (Y=xP) on G obtained by multiplying the P by x, then the proof support information t stored in the third memory is the data [t=xxe2x88x921 f (e, n, q, P, G) mod n] obtained by multiplying an inverse element xxe2x88x921 of the x by a non-conflictive function value f (e, n, q, P, G) which depends on the user unique identifying information e stored in the second memory means and also on the above n, q, P and G, under the modulus n, and for generating positive integers r an s as proof data, the proof data generation means may generate an appropriate random number k, assume that the value determined from point (=kP) obtained by multiplying the P by k on G is r, then use the authentication data m stored in the first memory means, as well as the above e, n, q, P, G and f (e, n, q, P, G), then subtract the product of f (e, n, q, P, G) and r from m and multiply the resulting difference by the inverse of k, under the modulus n, to generate s {=[mxe2x88x92rf(e, n, q, P, G)] kxe2x88x921 mod n}, while the proof data verification means, under the modulus n, may generate an inverse element w (=sxe2x88x921 mod n) of s, further generate the value wrt by multiplying the proof support information t stored in the third memory by the above r and w and the value wm by multiplying the above m by w, and verify that, on G, the value v determined from the value V (=wrtY+wmP) is equal to the above r under the modulus n (vxe2x89xa1r mod n) which value V is the sum of the value obtained by multiplying the Y by wrt and the value obtained by multiplying the P by wm.
The authentication data may be an output h(r) provided the random number r generated by the random number generation means is an input to the non-conflictive function h.
The present invention can be implemented as a method, or at least a portion thereof can be made a software implementing mode.